/*
 * @lc app=leetcode id=57 lang=cpp
 *
 * [57] Insert Interval
 */
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ret;
        int len = intervals.size();
        if (len < 1) {
            ret.push_back(newInterval);
            return ret;
        }
        int idx = 0;
        while (idx < len && intervals[idx][1] < newInterval[0]) {
            ret.push_back(intervals[idx]);
            idx ++;
        }

        while (idx < len && intervals[idx][0] <= newInterval[1]) {
            newInterval[0] = std::min(intervals[idx][0], newInterval[0]);
            newInterval[1] = std::max(intervals[idx][1], newInterval[1]);
            idx++;
        }

        ret.push_back(newInterval);

        while (idx < len) {
            ret.push_back(intervals[idx++]);
        }
        return ret;
        
    }
};

